\section{Introducci\'on}
Se nos pidi\'o implementar un algoritmo que determine la constuccion de centralitas de gas y tuberías tal que la longitud de la tuber\'ia mayor sea la minima posible, así minimizando el riesgo del proyecto. 
\\
El riesgo de cada posible proyecto biene dado por la longitud de la tuber\'ia mas larga en el mismo, por lo tanto sen\'a necesario calular la longitud de las tuber\'ias que une dos ciudades utilizando el teorema de pitagoras.
\\
De esa manera la longitud de una tuber\'a que une una ciudad $C_1 = (x_1,y_1)$ y otra $ C_2 = (x_2,y_2)$ es $$w(C_1,C_2) = \sqrt{(x_1 - x_2)^2 +(y_1 - y_2)^2}$$
\\
La entrada del algoritmo ser\'a la siguiente:
\begin{itemize}
\item Un entero \textbf{n} $\rightarrow$ Representar\'a el n\'umero de pueblos a conectar.
\item Un entero \textbf{k} $\rightarrow$ Representar\'a el n\'umero maximo de centrales de gas a construir.
\item $n$ pares de enteros $f_1,c_1,f_2,c_2,...,f_n,c_n\rightarrow$ Representar\'an las coordenadas de los $n$ pueblos.
\end{itemize}
La respuesta que el algoritmo deve devolver es:
\begin{itemize}
\item $q$ la cantidad de centrales construidas.
\item $m$ la cantidad de tuber\'ias construidas.
\item una linea con $q$ enteros que representar\'an los pueblos en los que se construiran centrales.
\item $m$ lineas con:
\begin{itemize}
\item $2$ enteros que representan el los pueblos entre los cuales construir tuber\'ias. 
\end{itemize}
\end{itemize}
\subsection{Ejemplo}
Por ejemplo una instancia valida de el problema puede ser:
$$n = 3,k=2$$
$$f_1 = 1,c_1 = 1$$
$$f_2= 2,c_2 = 2$$
$$f_3 = 10,c_3 = 10$$
\\ 
En este caso una solucion optima, aquella que minimiza la longitud de las tuber\'ia mas larga y por lo tanto el riesgo del proyecto, es:
\begin{itemize}
\item En el pueblo $1$ hay centralita.
\item En el pueblo $3$ hay centralita.
\item Entre el pueblo $1$ y $2$ se construye una tuber\'ia.
\item El riesgo es $\sqrt{(f_1 - f_2)^2 +(c_1 - c_2)^2} = \sqrt{ (1-2)^2+(1-2)^2} = \sqrt{2} $.
\end{itemize}
Puede verse que cualquier otra solucion es peor (en el caso de construir una tuber\'ia entre el pueblo 1 y el tres, por ejemplo) o igual (como el caso de poner la centralita en el pueblo $2$ en vez de en el pueblo $1$.
\\
Entonces lo que dever\'a devolver el algoritmo en este caso es:

\begin{itemize}
\item $k = 2, m = 1$
\item $1$ $3$
\item $1$ $2$
\end{itemize}


\section{Idea General de Resoluci\'on}
Para la soluci\'on del problema se modelizar\'a el problema como un grafo no dirigido completo, cuyos pesos en las aristas vienen dados por la funci\'on $w(C_1,C_2)$ antes descripta.
\\
Luego se debe buscar la manera de empezar a quitar aristas, tal que la arista de mayor peso en el grafo obtenido, sea la minima posible y que haya $k$ componentes conexas (en cada componente conexa hab\'a una central).
\\
De esta manera obtendremos la menor cantidad de aristas posibles $(n-k)$. Es facil notar en este punto que, con menos aristas, habr\'a algun pueblo que no tendr\'a gas, y con mas aristas, el riesgo del proyecto es potencialmente mayor (igual en el caso en que la arista de mayor peso tenga el mismo peso a la siguiente arista de mayor peso)
\\
Finalmente lo que el algoritmo har\'a es, se buscar un arbol generador minimo a travez del algoritmo de prim, y luego, quitando las $n-k$ aristas mas pesadas del grafo obtenido, se partir\'a este arbol en $k$ componentes conexas asi obteniendo una solucion optima. (notar que puede haber mas de una soluci\'on optima en el caso de que mas de una arista tenga el mismo peso y halla que desempatar de alguna manera)
\\
Ademas es posible realizar una pequeña optimizacion, ya que cuando $k \geq n$, la soluci\'on optima es trivial ya que es posible poner una central por pueblo y el riesgo del proyecto ser\'a $0$.
\\
Ahora mostraremos la idea general del algoritmo que aplicaremos de manera mas formal.
\\
\section{Pseudoc\'odigo}

\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void funcionPrincipal()}

  \STATE{int n, k}
  \STATE{Si $k \geq n$ devolver grafo con n vertices y sin aristas }
  \STATE{Crear grafo completo con pesos de las aristas iguales a la distancia entre pueblos}
  \STATE{Por Prim, crear, a partir del grafo completo, el arbol generador minimo, $G$}
  \STATE{\textbf{for j = 1; j < k; j++}}
    \STATE{\quad Elimino la arista mas pesada del grafo $G$}
  \STATE{Devolver $G$}

\end{algorithmic}
\end{algorithm}

\subsection{Ejemplo practico del algoritmo}
Utilizando el ejemplo mostrado antes:
$$n = 3,k=2$$
$$f_1 = 1,c_1 = 1$$
$$f_2= 2,c_2 = 2$$
$$f_3 = 10,c_3 = 10$$
\\
Aplicaremos el algoritmo descripto antes:
\\
 \indent Primero creamos el grafo completo:
\\
 \indent \indent $1-2$ Peso de la arista: $\sqrt{(f_1 - f_2)^2 +(c_1 - c_2)^2} =1.41421$
\\
 \indent \indent$1-3$ Peso de la arista: $\sqrt{(f_1 - f_3)^2 +(c_1 - c_3)^2} =12.7279$
\\
 \indent \indent $2-3$ Peso de la arista: $\sqrt{(f_3 - f_2)^2 +(c_3 - c_2)^2} =11.3137$
\\
 \indent Aplicamos prim y el grafo queda:
\\
 \indent \indent $1-2$ Peso de la arista: $\sqrt{(f_1 - f_2)^2 +(c_1 - c_2)^2} =1.41421$
\\
 \indent \indent $2-3$ Peso de la arista: $\sqrt{(f_3 - f_2)^2 +(c_3 - c_2)^2} =11.3137$
\\
 \indent para $j = 1$ mientras $j < k$
\\
 \indent \indent Elimino la arista mas pesada del arbol.
\\
 \indent \indent $j = j+1$
\\
 \indent El grafo queda:
\\
 \indent \indent$1-2$ Peso de la arista: $\sqrt{(f_1 - f_2)^2 +(c_1 - c_2)^2} =1.41421$
\\
 \indent Poniendo una central en cada componente conexa y con la arista obteinda, obtengo la soluci\'on.

\section{Cota de Complejidad}
Crear el grafo completo cuesta $O(n^2)$ ya que se debe calcular todos los pesos de una matriz de $n.n$.
\\
El algoritmo de prim, implementado con una matriz, cuesta $O(n^2)$.
\\
Luego se quitan $k-1$ aristas. Para ello itero $k-1$ veces las $n$ aristas, obtengo el maximo y lo elimino. Esto cuesta $O(k.n)$
\\
Finalmente el resultado: $O(n^2) + O(n^2) + O(k.n)$
\\
Pero recordando que el $k$ debe ser menor a $n$ ya que de otra manera es un caso trivial, entonces el peor caso es que $k = n-1$.
\\
Entonces: $O(n^2) + O(n^2) + O(n.(n-1)) = O(n^2)$

\section{Correctitud}
En esta secci\'on vamos a probar que el algoritmo descripto, crea un grafo tal que, la arista de peso maximo en el minimo, es la minima posible entre todos los grafos con $n-k$ aristas y $k$ componentes conexas, con $1 \leq k \leq n-1$.
\\
El caso $k < 1$ no tiene sentido, y el caso $k \geq n$ es tivial, ya que se devuelve simplemente el grafo sin aristas y esa es la solucion optima (ya que el riesgo es $0$) 
\\
Por induccion:
\\
Paso base $K= 1$
\\
En este caso el algoritmo solo crear\'a el grafo completo y luego realizar\'a el algoritmo de prim. Obtieniendo de esa manera un arbol generador minimo.
\\
Entre todas las aristas de este AGM tomo aquella de peso maximo, a la que llamo $e$, quiero probar que dado cualquier \'arbol generador $G'$ si tomo la arista mas pesada del mismo, a la que llamo $j$, se cumple que:
\\
$$w(e) \leq w(j)$$
\\
Primero defino una propiedad que utilizaré. Para cualquier corte $C$ en el grafo, si el peso de un eje $e$ de $C$ es estrictamente menor que los pesos de todos los otros ejes de $C$, entonces este eje, pertenece a todos los arboles generadores minimos del grafo.
\\
En un corte que incluye al eje $e$ (esto es, que separa a sus dos vertices adyacentes) sabemos que $e$ tiene que ser el eje con menor peso para ese corte.
\\
Cualquier arbol generador $G'$ tiene que tener al menos un eje de ese corte.
\\
Sea $e'$ ese eje. Sabemos que $$w(e') \geq w(e) $$
\\
Tambien sabemos que
\\
$$w(j) \geq w(e') $$
\\
Entonces
\\
$$w(j) \geq w(e') \geq w(e)$$
\\
Queda demostrado.
\\
\\
Paso inductivo:
\\
En este caso el algoritmo crear\'a el grafo completo, luego realizar\'a el algoritmo de prim para obtener un AGM y luego quita las $k$ aristas mas pesadas.
\\
Quiero probar que si el el algoritmo devuelve un bosque con $j-1$ componentes conexas tal que la arista de peso maximo en el minimo posible entre todos los bosques de $j-1$ componentes conexas, entonces el algoritmo devuelve un bosque con $j$ componentes conexas tal que la arista de peso maximo en el minimo posible entre todos los bosques de $j$ componentes conexas.
\\
Se que algoritmo devuelve un bosque $B$ con $j-1$ componentes conexas tal que la arista de peso maximo en el minimo posible entre todos los bosques de $j-1$ componentes conexas. Ahora el algoritmo quita la arista mas pesada. Ahora tengo un bosque $B'$ de $j$ componentes conexas y tal que su peso es el minimo posible. Esto es facil de ver ya que quitando cualquier otra arista, la arista mas pesada de $B'$ continúa siendo la arista mas pesada de $B$, si quito la arista mas pesada de $B'$ es claro que la arista mas pesada de $B'$ debe ser menor o igual.
\\
Luego queda demostrado.

\newpage
\section{Testing}

\subsection{Caso Random}
Ejemplo de caso random: (Este en particular tambi\'en fue verificado a mano)
\\
\begin{center} 
\begin{tabular}{| l | l |}
\hline
Entrada 
\\
10 4
\\
32 7
\\
29 13
\\
12 32
\\
12 26
\\
33 37
\\
2 30
\\
37 9
\\
30 12
\\
5 28
\\
38 2 \\ \hline
\end{tabular}
\begin{tabular}{| l | l |}
\hline
Salida
\\
4 6
\\
1
\\
4
\\
5
\\
9
\\
8 2
\\
4 3
\\
9 6
\\
1 7
\\
1 8
\\
7 10
\\ \hline
\end{tabular}
\end{center} 
\\
En el grafico puede verse como estan distribuidas las centrales:
\\
\begin{center} 
\includegraphics[width=9cm]{./LaCentralita/Caso_Random.png}
\end{center}
\\
\subsection{caso k mayor a n}
\begin{center} 
\begin{tabular}{| l | l |}
\hline
Entrada 
\\
10 11
\\
32 7
\\
29 13
\\
12 32
\\
12 26
\\
33 37
\\
2 30
\\
37 9
\\
30 12
\\
5 28
\\
38 2 \\ \hline
\end{tabular}
\begin{tabular}{| l | l |}
\hline
Salida
\\
10 0
\\
1
\\
2
\\
3
\\
4
\\
5
\\
6
\\
7
\\
8
\\
9
\\
10
\\ \hline
\end{tabular}
\end{center} 
\\
Distribucion de centrales:
\\
\begin{center} 
\includegraphics[width=9cm]{./LaCentralita/k_mayor.png}
\end{center}
\\
\subsection{caso k igual a $1$}
\begin{center} 
\begin{tabular}{| l | l |}
\hline
Entrada 
\\
5 1
\\
19 25
\\
36 25
\\
40 9
\\
31 11
\\
1 10
\\ \hline
\end{tabular}
\begin{tabular}{| l | l |}
\hline
Salida
\\
1 4
\\
1
\\
1 2
\\
4 3
\\
2 4
\\
1 5
\\ \hline
\end{tabular}
\end{center}
\\
Distribucion de centrales:
\\
\begin{center} 
\includegraphics[width=9cm]{./LaCentralita/k_igual_1.png}
\end{center}
\\
\newpage
\section{Resultados}

Para gr\'aficar los tiempos de ejcuci\'on de nuestro algoritmo se fue variando la cantidad de ciudades y la cantidad de centrales del problema y se obtivieron los siguientes resultados:
\\
\\
\includegraphics[width=18cm]{./LaCentralita/tiempoVsn.png}
\\
\includegraphics[width=18cm]{./LaCentralita/tiempoVsk.png}

Como podemos ver el tiempo de ejcuci\'on es constante con respecto a la cantidad de centrales y lineal con respecto a la cantidad de ciudades, dando asi una soluci\'on mejor que la teorica esperada.

\section{Recuperatorio del TP2}
\subsection{Punto 1}
La modificacion que devería hacerse es la siguiente:
\\
Se crea un arbol por prim como antes.
\\
Luego, se toma la arista mas pesada del grafo obtenido, se multiplica por la constante r.
\\
Si este valor es mayor que C, esto quiere decir que es mas barato construir una central mas que construir la tuber\'ia entre esos dos pueblos.
\\
En ese caso, se quita esa arista del grafo y agrega una central.
\\
Se realiza esto hasta que la arista mas pesada del grafo por la constante r es menor a C, lo que quiere decir que es mas barato construir la tuber\'ia mas pesada que otra central.
\\
El grafo obtenido es la soluci\'on.
\\
Descripto mas formalmente:
\\
\begin{algorithm}
\begin{algorithmic}[1]\parskip=1mm
\caption{void funcionPrincipal()}

  \STATE{int $n$, $k$}
  \STATE{Si $k \geq n$ devolver grafo con $n$ vertices y sin aristas }
  \STATE{Crear grafo completo con pesos de las aristas iguales a la distancia entre pueblos}
  \STATE{Por Prim, generar arbol generador minimo, $G$}
  \STATE{\textbf{Mientras la arista mas pesada del grafo $G$ * r > C}}
    \STATE{\quad Elimino la arista mas pesada del grafo $G$}
  \STATE{devolver $G$}
\end{algorithmic}
\end{algorithm}

\subsection{Punto 2}
Para probar la correctitud se deber\'ia probar que el grafo $G$ obtenido es tal que su arista maxima $e$ cumple que  $e*r\leq C$, esto significa que la construccion de la tuber\'ia mas cara entre dos ciudades es menor a la construccion de una nueva central, y que no existe un grafo con la misma cantidad de componentes conexas que $G$ tal que su arista de peso maximo es menor, en otras palabras, que no existe una manera mejor de conectar las ciudades de una manera mas barata.
\\
Esto podría ser probado de una manera similar a la ya vista en la seccion de correctitud, primero se prueba que para un arbol generador minimo tal que todas sus aristas cumplen $e*r\leq C$, es la solucion optima.
\\
Luego se prueba que si para un bosque con $j-1$ aristas que cumplen $e*r\geq C$ el algoritmo funciona, entonces para un bosque con $j$ aristas que cumplen $e*r\geq C$ el algoritmo tambien devuelve la socucion correcta.
\\
Finalmente queda demostrado..